package com.qrpcw.algorithms;

public class FindMaximumSubarraySum {
	private class Result{
		int low, high, sum;

		public Result(int low, int high, int sum){
			this.low = low;
			this.high = high;
			this.sum = sum;
		}
	}
	
	public static void main(String[] args) {
		int[] array = new int[]{13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
		FindMaximumSubarraySum test = new FindMaximumSubarraySum();
		Result result = test.FindMaximumSubarray(array, 0, array.length-1);
		System.out.println(
				"Low Position:" + result.low + " " + "High Position:" + result.high + " " + "Sum:" + result.sum);
	}
	
	public Result FindMaxCrossingSubarry(int[] A, int low, int mid, int high){
		int leftSum = -10000; //left -sum ,which holds the greatest sum found so far
		int maxLeft = 0;
		int sum = 0;
		for(int i=mid; i>=low; i--){
			sum = sum + A[i];
			if(sum > leftSum){
				leftSum =sum;
				maxLeft = i;
			//leftSum = (sum > leftSum)?sum:leftSum;
			}
		}
		int rightSum = -10000;
		int maxRight = 0;
		sum = 0;
		for(int j=mid+1; j<=high; j++){
			sum = sum + A[j];
			if(sum > rightSum){
				rightSum = sum;
				maxRight = j;
			}
		}
		return new Result(maxLeft, maxRight, leftSum+rightSum);
	}

	public Result FindMaximumSubarray(int[] A, int low, int high){
		if(high == low){
			return new Result(low, high, A[low]);
		}else{
			int mid = (low+high)/2;
			Result leftResult = FindMaximumSubarray(A, low, mid);
			Result rightResult = FindMaximumSubarray(A, mid+1, high);
			Result crossResult = FindMaxCrossingSubarry(A, low, mid, high);
			if(leftResult.sum >= rightResult.sum && leftResult.sum >= crossResult.sum){
				return new Result(leftResult.low, leftResult.high, leftResult.sum);
			}else if(rightResult.sum >= leftResult.sum && rightResult.sum >= crossResult.sum){
				return new Result(rightResult.low, rightResult.high, rightResult.sum);
			}else{
				return new Result(crossResult.low, crossResult.high, crossResult.sum);
			}
		}
	}
}
